package mao.leetcode.array.leetcode79;

public class Solution {

    boolean[][] isMark;
    int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
    int m ;
    int n ;
    char[] chars;

    public boolean exist(char[][] board, String word) {
        this.m = board.length;
        if (m == 0) return false;
        this.n = board[0].length;
        isMark = new boolean[m][n];
        chars=word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if( dfs(board,0, i, j))
                    return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,int index,int i,int j){
        if (index >= chars.length)  return true;
        if (check(m,n,i,j) && !isMark[i][j] && board[i][j] == chars[index]) {
            isMark[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newI = i + direction[k][0];
                int newJ = j + direction[k][1];
                if (dfs(board, index + 1, newI, newJ)) //此处需要注意，只有找到才返回。
                    return true;
            }
            isMark[i][j] = false;
        }
        return false;
    }

    public boolean check(int m,int n,int i,int j){
        return (i<m && i>=0 && j<n && j>=0);
    }
}
